package leetcode.剑指offer.前40;

import leetcode.剑指offer.pojo.TreeNode;
import org.junit.Test;

import java.util.*;

/**
 * @author :songyaozhang
 * @date :Created 2021/7/30 15:52
 * @description :
 */
public class 剑指_37_序列化二叉树 {
    @Test
    public void test() {
        Codec codec = new Codec();
        TreeNode root = new TreeNode(1, new TreeNode(2), new TreeNode(3, new TreeNode(4), new TreeNode(5)));
        String serialize = codec.serialize(root);
        System.out.println(serialize);
        TreeNode head = codec.deserialize(serialize);

    }

    public class Codec {

        // Encodes a tree to a single string.
        public String serialize(TreeNode root) {
            List<Integer> list = new ArrayList<>();
            if (root == null) return list.toString();
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            while (!queue.isEmpty()) {
                int size = queue.size();
                while (size > 0) {
                    TreeNode node = queue.poll();
                    if (node == null) {
                        list.add(null);
                        size--;
                        continue;
                    }
                    list.add(node.val);
                    queue.offer(node.left);
                    queue.offer(node.right);
                    size--;
                }
            }
            return list.toString();
        }


        // Decodes your encoded data to tree.
        public TreeNode deserialize(String data) {
            data = data.substring(1, data.length() - 1);
            if (data.length() == 0) return null;
            String[] nodes = data.split(",");
            Queue<TreeNode> queue = new LinkedList<>();
            TreeNode root = new TreeNode(Integer.parseInt(nodes[0].trim()));
            queue.offer(root);
            for (int i = 1; i < nodes.length; i++) {
                TreeNode node = queue.poll();
                if (" null".equals(nodes[i])) {
                    node.left = null;
                } else {
                    TreeNode left = new TreeNode(Integer.parseInt(nodes[i].trim()));
                    node.left = left;
                    queue.offer(left);
                }
                if (i + 1 < nodes.length) {
                    i++;
                    if (" null".equals(nodes[i])) {
                        node.right = null;
                    } else {
                        TreeNode right = new TreeNode(Integer.parseInt(nodes[i].trim()));
                        node.right = right;
                        queue.offer(right);
                    }
                }
            }
            return root;
        }
    }


}
